package traverse;

import java.util.*;

public class StrongConnect {
    private int numOfNode;
    private List<ArrayList<Integer>> graph;//图
    private List<ArrayList<Integer>> result;//保存极大强连通图
    private boolean[] inStack;//节点是否在栈内，因为在stack中寻找一个节点不方便。这种方式查找快
    private Stack<Integer> stack;
    private int[] dfn;//深度优先遍历 记录搜索到该结点的时间，也就是第几个搜索结点的
    private int[] low;//为该结点或该结点的子树能够追溯到的最早的栈中节点的次序号。
    private int time;//

    public StrongConnect(List<ArrayList<Integer>> graph, int numOfNode) {
        this.graph = graph;
        this.numOfNode = numOfNode;
        this.inStack = new boolean[numOfNode];
        this.stack = new Stack<>();
        dfn = new int[numOfNode];
        low = new int[numOfNode];
        Arrays.fill(dfn, -1);//将dfn所有元素都置为-1，其中dfn[i]=-1代表i还有没被访问过。
        Arrays.fill(low, -1);
        result = new ArrayList<>();
    }

    public List<ArrayList<Integer>> getResult() {
        for (int i = 0; i < numOfNode; i++) {
            if (dfn[i] == -1) {
                trajan(i);//-1代表没有被访问
            }
        }
        return result;
    }

    public void trajan(int current) {
        dfn[current] = low[current] = ++time;// 为节点current设定次序编号和Low初值
        stack.push(current); // 将节点u压入栈中
        inStack[current] = true;

        // 遍历当前结点的每一个结点
        for (int i = 0; i < graph.get(current).size(); i++) {
            //当前结点的下一个结点
            int next = graph.get(current).get(i);
            if (dfn[next] == -1) {//-1代表没有被访问
                //没有被访问过就继续递归遍历该结点的连通结点
                trajan(next);
                low[current] = Math.min(low[current], low[next]);
            } else if (inStack[next]) { // 如果节点next还在栈内
                low[current] = Math.min(low[current], dfn[next]);
            }
        }

        if (low[current] == dfn[current]) {// 如果节点u是强连通分量的根
            ArrayList<Integer> temp = new ArrayList<Integer>();
            int j = -1;
            while (current != j) {
                j = stack.pop();// 将v退栈，为该强连通分量中一个顶点
                inStack[j] = false;
                temp.add(j);
            }
            result.add(temp);
        }
    }
}
